#include <stdio.h>
#include <malloc.h>

typedef struct
{
	int *l;
	int len;
}list;


void display_list(list a)
{
	printf("[ ");
	int i;
	if(a.l !=0)
	{
	for (i=0; i < a.len -1; i++)
	{
		printf("%d, ", a.l[i]);
	}
	printf("%d ]\n", a.l[a.len-1]);
	}
	else
	{ printf(" ]\n"); }
}

void list_append(list *a, int num)
{
	if(a->len==0)
	{
		a->l = (int *)malloc(sizeof(int));
		a->l[0] = num;
		a->len++;
	}	
	else
	{
		a->l = (int *)realloc(a->l, (a->len+1)*sizeof(int));
		a->len++;
		a->l[a->len-1] = num;
	}	
}
void generate_list(list *a)
{
	printf("\nPlease enter the number of items you want to enter: ");
	int c, i, temp;
	int j;
	scanf("%d", &c);
	i = 1;	
	while(i<=c)
	{
		printf("\nElement %d: ", i);
		scanf("%d", &temp);
		list_append(a, temp);
		i++;
	}
}	


int list_pop(list *a, int index)
{
	
	if(a->len==0)
	{
		printf("\n\nERROR: The list doesn't have any elements! \n\n");
		return;
	}
	else if(index >= a->len || index < 0)
	{
		printf("\n\nERROR: Index out of range! \n\n");
		return;
	}
	else
	{
		int i, temp;
		temp = a->l[index];
		for (i=index + 1; i < a->len ; i++)
		{
			a->l[i-1] = a->l[i];
		}
		a->l = (int *)realloc(a->l, (a->len-1)*sizeof(int));
		a->len--;
		printf("\nYou popped the element: %d", temp);
		return temp;
	}
}

void list_extend(list *a)
{
	list b;
	b.l = NULL;
	b.len = 0;
	generate_list(&b);

	printf("\n\nList b is: ");
	display_list(b);

	printf("\nThe original list will now be extended using this newly formed list! \n");
	a->l = (int *)realloc(a->l, (a->len + b.len)*sizeof(int));
	int i=0;
	int t = a->len;
	while(i < b.len)
	{
		a->l[t + i] = b.l[i];
		i++;
		a->len++;
	}
	b.len = 0;
	free(b.l);
				
}

void list_remove(list *a)
{	
	int temp;
	printf("\nPlease enter the element to be removed: ");
	scanf("%d", &temp);
	
	int i=0, flag=0, index=0;
	for (i=0; i < a->len ; i++)
	{
		if(a->l[i]==temp){	flag = 1; index = i; break;}
	}
	if(flag==1)
	{
		for (i=index + 1; i < a->len ; i++)
		{
			a->l[i-1] = a->l[i];
		}
		a->l = (int *)realloc(a->l, (a->len-1)*sizeof(int));
		a->len--;		
	}
	else
	{
		printf("\nERROR: Element does not exist!\n");
		return;
	}

	
}

int list_index(list *a, int ele)
{
	int i=0;
	int index = -1;
	for (i=0; i<a->len ; i++)
	{
		if(a->l[i]==ele)
		{
			index = i;
			return index;
		}
	}

	return index;
}


int list_count(list *a, int ele)
{
	int i=0;	
	int count=0;
	for (i=0; i< a->len ; i++)
	{
		if(a->l[i]==ele)
		{
			count++;
		}
	}
	return count;
}

void list_sort(list *a)
{
	int i, j, small, temp;
	for (i=0; i < a->len ; i++)
	{
		small = i;
		for (j=i; j < a->len ; j++)
		{
			if((a->l[j]) < (a->l[small]))
			{ small = j; }
		}
		temp = a->l[small];
		a->l[small] = a->l[i];
		a->l[i]  = temp;
	}
}

void list_reverse(list *a)
{
	int i, t;
	for(i=0; i < a->len/2 ; i++)
	{
		t = a->l[i];
		a->l[i] = a->l[(a->len - i -1)];
		a->l[(a->len - i-1)] = t;
	}	
}

void list_insert(list *a, int i, int x)
{
	if(i> a->len)
	{ printf("\nInvalid Index!"); return; }
	
	if(i==a->len)
	{
		list_append(a, x);
	}
	else
	{
	a->len++;
	a->l = (int *)realloc(a->l, (a->len)*sizeof(int));
	
	int j;
	for(j = a->len-2 ; j >= i ; j--)
	{
		a->l[j+1] = a->l[j];
	}
	a->l[i] = x;
	}	
}
void main()
{
	list a; a.l = NULL; a.len = 0;

	generate_list(&a);
	int ch=1;

	printf("\n\n\t\t\tWelcome to the List Program!\n\t This program implements the list data structure using arrays!\n\n");

	while(ch!=0)
	{
	printf("\n\nPlease choose an option\n\t\t1. Append an Element\n\t\t2. Pop an Element\n\t\t3. Extend The List\n\t\t4. Remove an Element\n\t\t5. Find Index of an element\n\t\t6. Count the instances of an element\n\t\t7. Sort the list\n\t\t8. Reverse the List\n\t\t9. Insert an Element\n\t\t0. Exit");
	printf("\n\nCurrent state of list is: ");	
	display_list(a);
	printf("\nYour choice: ");
	scanf("%d", &ch);

	switch(ch){
	case 0:{ break; }
	case 1:{ printf("\nPlease enter the element you want to append: "); int temp; scanf("%d", &temp); list_append(&a, temp); break;}
	case 2:{ printf("\nPlease enter the index you want to pop: "); int temp; scanf("%d", &temp); list_pop(&a, temp); break;}
	case 3:{ list_extend(&a); break; }
	case 4:{ list_remove(&a); break; }
	case 5:{ int t; printf("Please enter the element who's index you want to find: "); scanf("%d", &t); int temp = list_index(&a, t); if(temp==-1) printf("\n\nThe Element doesn't exist!"); else {printf("\n\nThe index of the element is: %d", temp);} break;}
	case 6:{ int t; printf("Please enter the element who's count you want to find: "); scanf("%d", &t); int temp = list_count(&a, t); if(temp==0) printf("\n\nThe Element doesn't exist!"); else {printf("\n\nThe count of the element is: %d", temp);}  break;}
	case 7:{ list_sort(&a); break;}
	case 8:{ list_reverse(&a); break;}
	case 9:{ int i, x; printf("\nPlease enter the index at which you want to insert: "); scanf("%d", &i); printf("Please enter the element to insert: "); scanf("%d", &x); list_insert(&a, i, x); break;}
	default: { printf("\nInvalid choice!"); break; } }
	}

}
